package SW_438;

import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

public class Solution {
	public List<Integer> findAnagrams(String s, String p) {
		List<Integer> res = new LinkedList<Integer>();
		int left = 0, right = 0, match = 0;
		Map<Character, Integer> window = new HashMap<Character, Integer>();
		Map<Character, Integer> need = new HashMap<Character, Integer>();
		char[] SA = s.toCharArray();
		char[] PA = p.toCharArray();
		for (char c : PA) {
			need.put(c, need.getOrDefault(c, 0) + 1);
		}

		while (right < SA.length) {
			char key = SA[right];
			if (need.containsKey(key)) {
				window.put(key, window.getOrDefault(key, 0) + 1);
				if (window.get(key).compareTo(need.get(key)) == 0) {
					match++;
				}
			}
			right++;
			while (match == need.size()) {
				if (right - left == PA.length) {
					res.add(left);
				}
				char key2 = SA[left];
				if (need.containsKey(key2)) {
					window.put(key2, window.getOrDefault(key2, 1)-1);
					if (window.get(key2)<need.get(key2)) {
						match--;
					}
				}
				left++;
			}
		}
		return res;

	}
}
